package org.example.everyday;

/**
 * https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
 *
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 示例 1:

 输入: [3,2,1,5,6,4] 和 k = 2
 输出: 5
 示例 2:

 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 输出: 4

 */
public class FindKthLargest {

    public static void main(String[] args) {
        FindKthLargest find = new FindKthLargest();
        int[] arr = new int[]{3,2,1,5,6,4};
        int result = find.findKthLargest(arr,2);
        System.out.println(result);
    }

    public int findKthLargest(int[] nums, int k) {
        quickFind(nums,k,0,nums.length-1);
        return nums[k-1];
    }

    public void quickFind(int[] nums, int k, int start, int end){
       //递归的终止条件
        if(start>=end){
           return;
       }
        int pivot = nums[start];
        int left = start +1;
        int right = end;


        while (left <= right){
            if(nums[left] > pivot){
                left ++ ;
                continue;
            }
            if(nums[right] <= pivot){
                right --;
                continue;
            }
            swap(nums,left,right);
        }
        swap(nums,start,right);
        if(right - start + 1 == k){
            return;
        }
        if(right - start+1>k){
            quickFind(nums,k,start,right-1);
        }else{
            quickFind(nums,k-(left - start),left,end);
        }
    }


    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


}
